home *** CD-ROM | disk | FTP | other *** search
/ CD Ware Multimedia 1994 November / Cd Ware (Nro. 2) - Epimundo.iso / DOS / PG / STRX.ZIP / MATCH.CPP < prev    next >
Encoding:
C/C++ Source or Header  |  1994-01-14  |  15.5 KB  |  558 lines
  1. /*
  2.  *
  3.  * Author:    Allen I. Holub 
  4.  *
  5.  * (c) C Gazette. May be used freely as long as author and publication are
  6.  * acknowledged 
  7.  *
  8.  * Roy S. Woll                (Revision 2.1)
  9.  * 1032 Summerplace Dr.
  10.  * San Jose, CA 95122
  11.  *
  12.  * ----------------------------------------------------------------------
  13.  *
  14.  *
  15.  * Revision 2.31  14 Mar 1993 ROY S. WOLL
  16.  *
  17.  *   Fixed context sensitive match.  Now requires two "@".  Regular
  18.  *   expression compiling currently does not check this!
  19.  *
  20.  * Revision 2.11  14 Mar 1993 ROY S. WOLL
  21.  *
  22.  *   Fixed octal set definition to include first octel digit
  23.  *
  24.  * Revision 2.1   10 Dec 1992 ROY S. WOLL
  25.  *
  26.  *   Added support for PARAM which allows the user to specify which part
  27.  *   of the match should be saved.
  28.  *
  29.  * Revision 2.0   16 Nov 1992 ROY S. WOLL
  30.  *
  31.  *   Initial revision for match.c -> match.cpp
  32.  *   Compatibility with C++ syntax, and now member functions of regX.h
  33.  *   to avoid polluting the name space.
  34.  *   Fixed some inconsistencies. Regular expression compiled pattern should
  35.  *   now grow as needed.  Case insensitive support.
  36.  *
  37.  * Revision 1     27 Jan 1991 Allen I. Holub
  38.  *
  39.  */
  40.  
  41. #include <stdio.h>
  42. #include <ctype.h>
  43. #include <string.h>
  44.  
  45. #include "regximp.h"
  46.  
  47. inline const char * max(const char * x, const char * y)
  48.    {if (x>y) return x; else return y;}
  49.  
  50. /* Metacharacters in the input:         */
  51. #define BOL     '^'     /* start-of-line anchor                 */
  52. #define EOL     '$'     /* end-of-line anchor                   */
  53. #define ANY     '.'     /* matches any character                */
  54. #define CCL     '['     /* start a character class              */
  55. #define CCLEND  ']'     /* end a character class                */
  56. #define NCCL    '^'     /* negates character class if 1st char. */
  57. #define CLOSURE '*'     /* Kleene closure (matches 0 or more)   */
  58. #define PCLOSE  '+'     /* Positive closure (1 or more)         */
  59. #define OPT     '?'     /* Optional closure (0 or 1)            */
  60. #define PARAM   '@'     /* Save matches to buffer               */
  61.  
  62. typedef enum action {      // These are put in the pattern string
  63.                            // to represent metacharacters.
  64.   M_BOL =    (0x80 | '^'), 
  65.   M_EOL =    (0x80 | '$'),
  66.   M_ANY =    (0x80 | '.'),
  67.   M_CCL =    (0x80 | '['),
  68.   M_OPT =    (0x80 | '?'),
  69.   M_CLOSE =  (0x80 | '*'),
  70.   M_PCLOSE = (0x80 | '+'),
  71.   M_PARAM =  (0x80 | '@')
  72.  
  73. } action;
  74.  
  75.  
  76.  
  77. typedef unsigned char pattern;   /* pattern strings are unsigned char */
  78.  
  79. #define IS_ACTION(x) ((x)&0x80)  /* true => element of pat. string is an   */
  80.                                 /* action that represents a metacharacter */
  81.  
  82. /*----------------------------------------------------------------------*/
  83. #define MAPSIZE 16  /* need this many bytes for character class bit map */
  84.  
  85. /*
  86.  * Advance a pointer into the pattern template 
  87.  * to the next pattern element, this is a +1 for
  88.  * all pattern elements but M_CCL, where you
  89.  * to skip past both the M_CCL character and the
  90.  * bitmap that follows that character
  91.  */
  92.  
  93. #define ADVANCE(pat) (pat += (*pat == (pattern)M_CCL) ? (MAPSIZE+1) : 1)
  94.  
  95. //
  96. // Bitmap functions. Set bit b in the map and
  97. // test bit b to see if it was set previously.
  98. //
  99. #define SETBIT(b,map) ((map)[((b) & 0x7f) >>3] |= (1<< ((b) & 0x07)) )
  100. #define TSTBIT(b,map) ((map)[((b) & 0x7f) >>3] &  (1<< ((b) & 0x07)) )
  101.  
  102. int regXimp::omatch(const char ** strp, const pattern * pat, 
  103.                      const char * start)
  104. {
  105.   /*
  106.    * Match one pattern element, pointed at by pat, against the character at
  107.     * **strp. Return 0 on a failure, 1 on success. *strp is advanced to skip
  108.    * over the matched character on a successful match. Closure is handled one
  109.    * level up by patcmp(). 
  110.    *
  111.    * "start" points at the character at the left edge of the line. This might
  112.    * not be the same thing as *strp if the search is starting in the middle
  113.     * of the string. An end-of- line anchor matches '\n' or '\0'.
  114.    */
  115.  
  116.   int advance = -1;        // amount to advance *strp, -1 == error
  117.  
  118.   switch (*pat) {
  119.   case M_BOL:              // First char in string?
  120.     if (*strp == start)    // Only one star here.
  121.       advance = 0;
  122.     break;
  123.  
  124.   case M_ANY:              // . = anything but newline
  125.     if (**strp != '\n') advance = 1;
  126.      break;
  127.  
  128.   case M_EOL:
  129.     if (**strp == '\n' || **strp == '\0')
  130.       advance = 0;
  131.     break;
  132.  
  133.   case M_CCL:
  134.     if (TSTBIT(**strp, pat + 1)) advance = 1;
  135.     break;
  136.  
  137.   default:                 // literal match
  138.     if (caseSensitive){
  139.       if (**strp == *pat) advance = 1;
  140.     }
  141.     else if (toupper(**strp) == toupper(*pat)) advance = 1;
  142.     break;
  143.   }
  144.  
  145.   if (advance > 0)
  146.     *strp += advance;
  147.  
  148.   return (advance + 1);
  149. }
  150.  
  151. #define ISOCTDIGIT(x) ('0'<=(x) && (x)<='7')
  152.  
  153. static int hex2bin(int c)
  154. {
  155.      /* Convert the hex digit represented by 'c' to an int. 'c'
  156.       * must be one of: 0123456789abcdefABCDEF
  157.       */
  158.      return (isdigit(c) ? (c)-'0': ((toupper(c))-'A')+10)  & 0xf;
  159. }
  160.  
  161. static int oct2bin(int c)
  162. {
  163.      /* Convert the hex digit represented by 'c' to an int. 'c'
  164.         * must be a digit in the range '0'-'7'.
  165.       */
  166.      return ( ((c)-'0')  &  0x7 );
  167. }
  168.  
  169.  
  170.  
  171. /*------------------------------------------------------------*/
  172.  
  173. int     esc(const char **s)
  174. {
  175.      /* Map escape sequences into their equivalent symbols. Return
  176.       * the equivalent ASCII character. *s is advanced past the
  177.       * escape sequence. If no escape sequence is present, the
  178.       * current character is returned and the string is advanced by
  179.       * one. The following are recognized:
  180.       *
  181.       *  \b     backspace
  182.       *  \f     formfeed
  183.         *  \n     newline
  184.       *  \r     carriage return
  185.       *  \s     space
  186.       *  \t     tab
  187.       *  \e     ASCII ESC character ('\033')
  188.       *  \DDD   number formed of 1-3 octal digits
  189.         *  \xDDD  number formed of 1-3 hex digits
  190.       *  \^C    C = any letter. Control code
  191.       */
  192.  
  193.      int rval;
  194.  
  195.      if( **s != '\\' )
  196.           rval = *( (*s)++ );
  197.      else {
  198.           ++(*s);                               // Skip the '\'
  199.           switch( toupper(**s) ) {
  200.             case '\0':  rval = '\\';             break;
  201.             case 'B':   rval = '\b' ;            break;
  202.                 case 'F':   rval = '\f' ;            break;
  203.             case 'N':   rval = '\n' ;            break;
  204.             case 'R':   rval = '\r' ;            break;
  205.             case 'S':   rval = ' '  ;            break;
  206.             case 'T':   rval = '\t' ;            break;
  207.             case 'E':   rval = '\033';           break;
  208.  
  209.             case '^':   
  210.               rval = *++(*s) ;
  211.               rval = toupper(rval) - '@' ;
  212.               break;
  213.  
  214.             case 'X':   
  215.               rval = 0;
  216.               ++(*s);
  217.               if( isxdigit(**s) ) {
  218.                    rval  = hex2bin( *(*s)++ );
  219.               }
  220.               if( isxdigit(**s) ) {
  221.                          rval <<= 4;
  222.                    rval  |= hex2bin( *(*s)++ );
  223.               }
  224.               if( isxdigit(**s) ) {
  225.                    rval <<= 4;
  226.                    rval  |= hex2bin( *(*s)++ );
  227.                   }
  228.               --(*s);
  229.               break;
  230.  
  231.             default:
  232.               if( !ISOCTDIGIT(**s) )
  233.                    rval = **s;
  234.               else {
  235. //                   ++(*s);
  236.                    rval = oct2bin( *(*s)++ );
  237.                    if( ISOCTDIGIT(**s) ) {
  238.                         rval <<= 3;
  239.                         rval  |= oct2bin( *(*s)++ );
  240.                          }
  241.                    if( ISOCTDIGIT(**s) ) {
  242.                         rval <<= 3;
  243.                         rval  |= oct2bin( *(*s)++ );
  244.                    }
  245.                    --(*s);
  246.                   }
  247.               break;
  248.           }
  249.           ++(*s);
  250.      }
  251.      return rval;
  252. }
  253.  
  254.  
  255. /*----------------------------------------------------------------------*/
  256. const char * regXimp::doccl(const char * src)
  257. {
  258.   /*
  259.     * Set bits in the map corresponding to characters specified in the src
  260.    * character class.  
  261.    */
  262.  
  263.  
  264.   int                first, last, negative;
  265.  
  266.   ++src;                        // skip past the [
  267.   negative = (*src == NCCL);
  268.   if (negative) ++src;          // check for negative ccl
  269.  
  270.   const char * start = src;     // start of characters in class
  271.  
  272.   int len = compiledPattern.length();
  273.   compiledPattern.pad(len+MAPSIZE, str::right, char(0));
  274.   char * map = (char *)compiledPattern(len);
  275.  
  276.   while (*src && *src != CCLEND) {
  277.     if (*src != '-') {
  278.         first = esc(&src);        // Use temp. to avoid macro
  279.                                 // side effects.
  280.       SETBIT(first, map);  
  281.  
  282.     } else if (src == start) {
  283.       SETBIT('-', map);         // literal dash at start or end
  284.         ++src;
  285.     } else {
  286.       ++src;                    // skip to end-of-sequence char
  287.  
  288.      // Support special characters within [].
  289.       last = esc(&src);   
  290.       if (last < first){
  291.          int temp=first;
  292.          first = last;
  293.          last = temp;
  294.       };
  295.  
  296.       while (++first <= last) SETBIT(first, map);
  297.      }
  298.   }
  299.  
  300.   if (*src == CCLEND) ++src;    // Skip CCLEND
  301.  
  302.   if (negative)
  303.      for (first = MAPSIZE; --first >= 0;)
  304.       *map++ ^= ~0;     /* invert all bits */
  305.  
  306.   return src;
  307. }
  308.  
  309. /*----------------------------------------------------------------------*/
  310. const char * regXimp::patcmp(const char * sstr, const pattern * pat, 
  311.            const char * start, int curMatch)
  312. {
  313.   /*
  314.    * Like strcmp, but compares str against pat. Each element of str is
  315.    * compared with the template until either a mis-match is found or the end
  316.     * of the template is reached. In the former case a 0 is returned; in the
  317.    * latter, a pointer into str (pointing to the last character in the
  318.    * matched pattern) is returned. Strstart points at the first character in
  319.    * the string, which might not be the same thing as line if the search
  320.    * started in the middle of the string. 
  321.    */
  322.  
  323.   const char     *bocl;    // beginning of closure string.
  324.   const char     *end=0;   // return value: end-of-string pointer.
  325.  
  326.   if (!pat) return (NULL); // make sure pattern is valid
  327.  
  328.   while (*pat) {
  329.     if (*pat == (pattern)M_PARAM) {
  330.          if (curMatch>=0) {  // currently in match, so save end
  331.              endMatch = sstr-1;
  332.              curMatch = -1;
  333.          }
  334.          else {             // flag start of match
  335.              startMatch = sstr; //endMatch = 0;
  336.              curMatch = 0;
  337.          };
  338.          pat++;
  339.          continue;  // this command still needs analysis !!!!
  340.      };
  341.  
  342.      if (*pat == (pattern)M_OPT) {
  343.         /*
  344.          * Zero or one matches. It doesn't matter if omatch fails---it will
  345.          * advance str past the character on success, though. Always advance
  346.          * the pattern past both the M_OPT and the operand.
  347.          */
  348.  
  349.         omatch(&sstr, ++pat, start);
  350.  
  351.         ADVANCE(pat);
  352.      } else if (!(*pat == (pattern)M_CLOSE || *pat == (pattern)M_PCLOSE)) {
  353.  
  354.       //
  355.       // Do a simple match. Note that omatch() fails if there's still
  356.       // something in pat but we're at end of string.
  357.       //
  358.         if (!omatch(&sstr, pat, start)) return NULL;
  359.  
  360.         ADVANCE(pat);
  361.  
  362.      } else {         // Process a Kleene or positive closure
  363.  
  364.         if (*pat++ == (pattern)M_PCLOSE) // one match required
  365.           if (!omatch(&sstr, pat, start)) return NULL;
  366.  
  367.  
  368.       // toggle match indicator
  369.         if (*pat == (pattern)M_PARAM){
  370.             if (curMatch>=0) curMatch = -1;
  371.             else curMatch=0;
  372.         };
  373.  
  374.       // Match as many as possible, zero is okay
  375.         bocl = sstr;
  376.         while (*sstr && omatch(&sstr, pat, start));
  377.  
  378.         /*
  379.          * 'str' now points to the character that made made us fail. Try to
  380.          * process the rest of the string. If the character following the
  381.          * closure could have been in the closure (as in the pattern "[a-z]*t")
  382.          * the final 't' will be sucked up in the while loop. So, if the match
  383.          * fails, back up a notch and try to match the rest of the string
  384.          * again, repeating this process recursively until we get back to the
  385.          * beginning of the closure. The recursion goes, at most, one levels
  386.          * deep.
  387.          */
  388.  
  389.  
  390.         if (*ADVANCE(pat)) {
  391.           do {
  392.              end = patcmp(sstr, pat, start, curMatch);
  393.              if (end) break;
  394.              sstr--;
  395.           } while (bocl <= sstr);
  396.           return end;
  397.         }
  398.  
  399.      break;
  400.      };
  401.  
  402.   }
  403.  
  404.   /*
  405.     * omatch() advances str to point at the next character to be matched. So
  406.     * str points at the character following the last character matched when
  407.     * you reach the end of the template. The exceptions are templates
  408.     * containing only a BOLN or EOLN token. In these cases omatch doesn't
  409.     * advance. Since we must return a pointer to the last matched character,
  410.     * decrement str to make it point at the end of the matched string, making
  411.     * sure that the decrement hasn't gone past the beginning of the string.
  412.     *
  413.     * Note that $ is a position, not a character, but in the case of a pattern
  414.     * ^$, a pointer to the end of line character is returned. In ^xyz$, a
  415.     * pointer to the z is returned.
  416.     *
  417.     * The --str is done outside the return statement because max() is a macro
  418.     * with side-effects.
  419.     */
  420.  
  421.   --sstr;
  422.  
  423.   return (max(start, sstr));
  424. }
  425.  
  426.  
  427. /*----------------------------------------------------------------------*/
  428. int regXimp::makepat(const char * exp)
  429. {
  430.   /*
  431.    * Make a pattern template from the string pointed to by exp. 
  432.    * The pattern template is assembled in str compiledPattern.  
  433.    * Regular expression can contain one or more \n characters.
  434.    *
  435.    * Return 1 if success
  436.    */
  437.  
  438.   error = 1;
  439.  
  440.   if (!*exp) goto exit;
  441.  
  442.   if (*exp == CLOSURE || *exp == PCLOSE || *exp == OPT) goto exit;
  443.  
  444.   int prev, len;
  445.  
  446.   len=0;
  447.  
  448.   while (*exp ) {
  449.  
  450.     switch (*exp) {
  451.     case ANY:
  452.       prev=len++;
  453.       compiledPattern += (pattern)M_ANY;
  454.       ++exp;
  455.       break;
  456.  
  457.     case PARAM:
  458.       prev=len++;
  459.       compiledPattern += (pattern)M_PARAM;
  460.       ++exp;
  461.       break;
  462.  
  463.      case BOL:
  464.       prev=len++;
  465.       compiledPattern += (!compiledPattern.length()) ? (pattern)M_BOL : *exp;
  466.         ++exp;
  467.       break;
  468.  
  469.     case EOL:
  470.       prev=len++;
  471.       compiledPattern += (!exp[1] || exp[1] == '\n') ? (pattern)M_EOL : *exp;
  472.       ++exp;
  473.       break;
  474.  
  475.     case CCL:
  476.       prev=len++;
  477.       compiledPattern += (pattern)M_CCL;
  478.       exp = doccl(exp);
  479.       len += MAPSIZE;
  480.       break;
  481.  
  482.      case OPT:
  483.     case CLOSURE:
  484.     case PCLOSE:
  485.         switch (compiledPattern[prev]) {
  486.         case M_BOL:
  487.         case M_EOL:
  488.         case M_OPT:
  489.         case M_PCLOSE:
  490.         case M_CLOSE:
  491.           goto exit;
  492.       }
  493.  
  494.       compiledPattern.insert(prev,
  495.               (*exp == OPT) ? (pattern)M_OPT :
  496.               (*exp == PCLOSE) ? (pattern)M_PCLOSE : (pattern)M_CLOSE);
  497.  
  498.       len++;
  499.       ++exp;
  500.       break;
  501.  
  502.     default:
  503.       prev=len++;
  504.         compiledPattern += esc(&exp);
  505.       break;
  506.     }
  507.   }
  508.  
  509.   error = 0;
  510.  
  511.  exit:
  512.   return (!error);
  513. }
  514.  
  515. /*----------------------------------------------------------------------*/
  516. const char * regXimp::matchs(const char * sstr, int p_case)
  517. {
  518.   const char     *endp = NULL;
  519.   const char     *start;
  520.   const unsigned char * pat = (unsigned char *)compiledPattern();
  521.  
  522.   int curMatch = -1;
  523.   caseSensitive = p_case;
  524.   startMatch = 0;
  525.   endMatch = 0;
  526.  
  527.   if (!pat) return NULL;
  528.  
  529.   if (*sstr == '\0') {
  530.     if ((*pat == (pattern)M_EOL) || 
  531.         (*pat == (pattern)M_BOL && (!pat[1] || pat[1] == (pattern)M_EOL)))
  532.     {
  533.       endp = sstr;
  534.       endMatch = startMatch = sstr;
  535.     }
  536.   } 
  537.   else {
  538.     start = sstr;    // Do a brute-force substring search,
  539.                             // comparing a pattern against the input string
  540.  
  541.     while (*sstr) {
  542.         endp = patcmp(sstr, pat, start, curMatch);
  543.  
  544.       if (endp) {
  545.          if (!endMatch) {
  546.             endMatch = endp;
  547.             startMatch = sstr;
  548.          };
  549.  
  550.          break;
  551.       };
  552.       sstr++;
  553.     }
  554.   }
  555.   return endp;
  556. }
  557.  
  558.